首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数：2367261 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 ， 矩阵中的值满足
进阶：空间复杂度 ，时间复杂度
示例1

输入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

true

说明

存在7，返回true
示例2

输入

1,[[2]]

输出

false
示例3

输入

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

false

说明

不存在3，返回false
算法知识视频讲解
添加回答
推荐
徘徊的路人甲头像 徘徊的路人甲 
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int rowCount = array.size();
        int colCount = array[0].size();
        int i,j;
        for(i=rowCount-1,j=0;i>=0&&j<colCount;)
        {
            if(target == array[i][j])
                return true;
            if(target < array[i][j])
            {
                i--;
                continue;
            }
            if(target > array[i][j])
            {
                j++;
                continue;
            }
        }
        return false;
    }
};

编辑于 2015-06-18 16:50:07 回复(249)
Python 3
范困粥头像 范困粥 
偷懒
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        for i in array:
            if i and i[0] <= target and i[-1] >= target:
                if not (self.search(i, target=target) is None):
                    return True
        return False

    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if len(nums) == 1:
            return 0 if nums[0] == target else None
        left = 0
        right = len(nums) - 1
        while left <= right:
            tmp = (left + right) // 2
            if nums[tmp] == target:
                return tmp
            elif nums[tmp] > target:
                right = tmp - 1 
            else:
                left = tmp + 1

        

发表于 2023-05-28 14:41:20 回复(0)
Python 3
well0-0头像 well0-0
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        while array:
            if target in array[0]:
                return True
            else:
                array.pop(0)
        return False
发表于 2023-03-26 18:41:39 回复(0)
Python 3
匿名牛由头像 匿名牛由
每一维的数组都是有序的，如果当前的数已经大于target，则后面的数也必然大于target 
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        i, j = 0, 0
        for arr in array:
            for num in arr:
                if num > target:
                    break
                if num == target:
                    return True
        return False

发表于 2023-03-12 10:29:32 回复(0)
Python 3
纳爱斯牛牛乐头像 纳爱斯牛牛乐
从数组右上角往左下角遍历每个元素i，如果i大于target则往左走，i小于target则往左走. 
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        if array==[[]]:
            return False
        n, m = 0, len(array[0])-1 # 右上角坐标
        while array[n][m]!=target and m>0 and n<len(array)-1:
            if array[n][m]>target: # 如果数比target大，则往左走
                m -= 1
            if array[n][m]<target: # 如果数比target小，则往下走
                n += 1
        return (array[n][m]==target)
发表于 2022-09-11 18:03:57 回复(0)
Python 3
JianYue头像 JianYue 
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        rows = len(array) - 1
        cols = len(array[0]) - 1
        if rows < 0&nbs***bsp;cols < 0:
            return False
        m, n = rows, 0
        while m >= 0 and n <= cols:
            cur = array[m][n]
            if cur == target:
                return True
            elif cur > target:
                m = m - 1
            elif cur < target:
                n = n + 1
        return False

发表于 2022-09-10 21:23:56 回复(0)
Python 3
想要offer的奶酪很健谈头像 想要offer的奶酪很健谈 
# 双二分查找
#   一维的二分查找可以舍弃一半的查找范围，二维的二分查找可以舍弃左上部分或者右下部分1/4的查找范围，具体看牛客
#   时间复杂度O(logM*logN) 空间复杂度O(1)

class Solution:
    def double_binary(self, target, array, x1, x2, y1, y2):
        if x1 <= x2 and y1 <= y2:
            xmid = (x1 + x2) // 2
            ymid = (y1 + y2) // 2
            m = array[xmid][ymid]
            if target == m:
                return True
            elif target < m:
                if self.double_binary(target, array, x1, xmid-1, y1 ,y2): return True
                if self.double_binary(target, array, xmid, x2, y1 ,ymid-1): return True
            else:
                if self.double_binary(target, array, x1, x2, ymid+1 ,y2): return True
                if self.double_binary(target, array, xmid+1, x2, y1 ,ymid): return True
        else:
            return False

    def Find(self, target, array):
        if not array: return False
        x2 = len(array) - 1
        y2 = len(array[0]) - 1
        if self.double_binary(target, array, 0, x2, 0, y2):
            return True
        else:
            return False


if __name__ == '__main__':
    Sol = Solution()
    print(Sol.Find(4,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]))

发表于 2022-09-02 11:21:35 回复(0)
Python 3
木有粗面201904101731812头像 木有粗面201904101731812
直接使用dfs， 超时了 
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # dfs
        def findHelper(raw, col, target, mr, mc):
            if raw > mr - 1&nbs***bsp;col > mc - 1&nbs***bsp;array[raw][col] > target: return False
            elif array[raw][col] == target: return True
            else:
                return findHelper(raw + 1, col, target, mr, mc)&nbs***bsp;findHelper(raw, col + 1, target, mr, mc)
        
        mr = len(array)
        mc = len(array[0])
        return findHelper(0, 0, target, mr, mc)



发表于 2022-08-22 15:28:36 回复(0)
Python 3
小Rzz头像 小Rzz
人蠢，只会for循环
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        res=[]
        for i in range(len(array)):
            res += array[i]
        if target in res :
            return True
        else:
            return False
发表于 2022-08-21 21:08:09 回复(0)
Python 3
新的一天，啦啦啦头像 新的一天，啦啦啦 
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        if not array:
            return False
        row = len(array)-1
        col = len(array[0])-1
        # 从右上角开始找
        start_row = 0
        start_col = col
        while start_row <= row and start_col > -1:
            if target < array[start_row][start_col]:
                start_col -= 1
            elif target > array[start_row][start_col]:
                start_row += 1
            else:
                return True
        return False


发表于 2022-08-21 15:50:07 回复(0)
Python 3
Z.201906050900995头像 Z.201906050900995
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        for i in range(len(array)):
            for a in range(len(array[i])):
                if array[i][a] == target:
                    return True
        return False
发表于 2022-08-18 07:43:30 回复(0)
Python 3
王明朗找工作头像 王明朗找工作
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here

        if array ==None:
            return False

        else:
            for i in array:
                while target in i:
                    return True
                    break
            return False
发表于 2022-08-15 21:24:45 回复(0)
Python 3
牛客163706763号头像 牛客163706763号
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        
        # write code here
        
        for item in array:
            for j in item:
                if target in item:
                    return True
        return False
发表于 2022-08-10 12:58:15 回复(0)
Python 3
ArthurMorgan*头像 ArthurMorgan* 
class Solution:
    def Find(self, target: int, array: List[List[int]]) -> bool:
        # write code here
        li = []
        for i in array:
            for j in i:
                li.append(j)
        if target in li:
            return True
        else:
            return False


发表于 2022-08-08 16:33:18 回复(0)
Python 3
pavelchen头像 pavelchen
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        for i in range(len(array)):
            l = 0
            r = len(array[i]) - 1
            while l <= r:
                mid = (int)((l + r)/2)
                if array[i][mid] == target:
                    return True
                elif array[i][mid] < target:
                    l = mid + 1
                elif array[i][mid] > target:
                    r = mid - 1
        return False
发表于 2022-08-02 11:40:39 回复(0)
Python 3
搞子哥头像 搞子哥 
        for i in list:
            if i == target:
                return True
        return False
为什么上面的能通过，下面的没办法通过呢 
        for i in list:
            if i == target:
                return True
            else:
                return False


发表于 2022-08-02 00:10:26 回复(0)
Python 3
牛客213220802号头像 牛客213220802号
python:
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        # 第一个方法，把二维数组转变为一维数组，然后去查找目标值是否存在
        arr_len = len(array)
        new_arr = []
        for i in range(arr_len):
            for j in array[i]:
                new_arr.append(j)
        if target in new_arr:
            return True
        else:
            return False

发表于 2022-07-28 18:59:45 回复(0)
Python 3
左空一头像 左空一 
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        for i in array:
            if target in i:
                return True
        return False

发表于 2022-07-26 17:10:04 回复(0)
Python 3
test8794头像 test8794
二维变一维，二分。
发表于 2022-07-20 14:24:28 回复(0)
提交观点

问题信息

数组
来自：2015年度信息化技能...
难度：
59条回答 1521004浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号